package com.likou.second_challenge;

import java.util.HashMap;
import java.util.Map;

public class q146 {
    class LRUCache {

        private class LRUNode {
            private LRUNode pre;
            private LRUNode next;
            private int key;
            private int value;

            public LRUNode() {

            }

            public LRUNode(int key, int value) {
                this.pre = null;
                this.next = null;
                this.key = key;
                this.value = value;
            }
        }

        private Map<Integer, LRUNode> cache;
        private int capacity;
        private LRUNode head;
        private LRUNode tail;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap<>();
            this.head = new LRUNode(0, 0);
            this.tail = new LRUNode(0, 0);
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            if (!cache.containsKey(key)) {
                return -1;
            }
            LRUNode lruNode = cache.get(key);
            // 移到头部
            delete(lruNode);
            moveToHead(lruNode);
            return lruNode.value;
        }

        public void put(int key, int value) {
            LRUNode lruNode = new LRUNode(key, value);
            if (!cache.containsKey(key)) {
                cache.put(key, lruNode);
                // 移到头部
                moveToHead(lruNode);
            } else {
                LRUNode old = cache.get(key);
                delete(old);
                old.value = value;
                moveToHead(old);
                cache.put(key, lruNode);
            }

            if (cache.size() > capacity) {
                cache.remove(tail.pre.key);
                delete(tail.pre);
            }
        }

        private void delete(LRUNode lruNode) {
            lruNode.pre.next = lruNode.next;
            lruNode.next.pre = lruNode.pre;
            lruNode.pre = null;
            lruNode.next = null;
        }

        private void moveToHead(LRUNode lruNode) {
            lruNode.pre = head;
            lruNode.next = head.next;
            head.next.pre = lruNode;
            head.next = lruNode;
        }
    }
}
